#include "binary_tree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "../global.h"
//#include "../stack/stack.h"

#define DFSWITH_STACKSIZE   100
#define QUEUE_SIZE 100

/**
 * 二叉树创建
 * 二叉树判空
 * 二叉树的前中后序遍历
 * 二叉树最大深度
 * 二叉树叶子节点的深度
 * 广度优先搜索
 * 深度优先搜索
 * 使用栈模拟深度优先搜索
 *
 * 二叉搜索树及其他二叉树也放在这里就不单独一个文件夹了
 * */

/**
 * 二叉树的创建
 * 1-创建成功 0-创建失败
 * 输入0表示没有该节点
 * */
int CreateTree(BITNODE** treeNode)
{
	int ch;
	int temp = 0;
	scanf("%d",&ch);
	if(ch == 0)
	{
		*treeNode = NULL;
	}
	else
	{
		*treeNode = (BITNODE*)malloc(sizeof(BITNODE));
		if( *treeNode == NULL )
		{
			//堆空间异常，抛异常
			printf("No enough heap space!\n");
		}
		else
		{
			(*treeNode)->data = ch;
			printf("请输入节点%d的左节点的值",ch);
			CreateTree(&(*treeNode)->lChild);
			printf("请输入节点%d的右节点的值",ch);
			CreateTree(&(*treeNode)->rChild);
		}

		return 1;
	}
	return 0;
}

/**
 * 前序遍历
 *
 * */
void PreOrder(const BITNODE* const treeNode)
{
	if(treeNode == NULL) return ;
	printf("%d ",treeNode->data);
	PreOrder(treeNode->lChild);
	PreOrder(treeNode->rChild);
}

/**
 * 中序遍历
 * */
void MidOrder(const BITNODE* const treeNode)
{
	if(treeNode == NULL) return ;
	MidOrder(treeNode->lChild);
	printf("%d ",treeNode->data);
	MidOrder(treeNode->rChild);

}

/**
 * 后序遍历
 * */
void PostOrder(const BITNODE* const treeNode)
{
	if(treeNode == NULL) return ;
	PostOrder(treeNode->lChild);
	PostOrder(treeNode->rChild);
	printf("%d ",treeNode->data);
}

/**
 * 求二叉树深度
 * 注意这个递归的返回值
 * */
int TreeDeep(const BITNODE* const treeNode)
{
	int deep = 0;
 	int leftDeep = 0,rightDeep = 0;
 	if(treeNode != NULL)
 	{
 		leftDeep = TreeDeep(treeNode->lChild);
 		rightDeep = TreeDeep(treeNode->lChild);
 		deep = leftDeep>=rightDeep?leftDeep+1:rightDeep+1;
 	}
 	return deep;

}

/**
 * 求二叉树叶子节点个数
 * 传入的num一开始要初始化为0
 * */
void LeafCount(BITNODE* treeNode,int* const num)
{
	if(treeNode != NULL)
	{
		if(treeNode->lChild == NULL && treeNode->rChild == NULL)
		{
			(*num)++;
		}
		LeafCount(treeNode->lChild,num); //先遍历左节点
		LeafCount(treeNode->rChild,num); //再遍历右节点
	}
	//return *num;
}

/**
 * DFS 深度优先搜索(遍历) 感觉有点类似中序遍历
 * 使用递归
 * */
void DFS(BITNODE* treeNode)
{
	if(treeNode == NULL) return ;
	DFS(treeNode->lChild);
	printf("%d ",treeNode->data);
	DFS(treeNode->rChild);
}

/**
 * DFS
 * 使用栈模拟递归过程
 * */
/* 发现stack.h中的数据结构和当下场景不兼容，而且函数也不兼容，除非重新写 */
/* 或者改一下相关的类型 */
typedef struct stack
{
    BITNODE**  stkPointer; //内存的地址
    int   size; //栈的大小
    int   top; //栈顶
}STACK;

/*
* 0-fail 1-success,如果入栈的数据是char类型咋办？用指针？const int* const data
*/
int PushStackBit(STACK* stk, BITNODE* const data)
{
	if(stk->stkPointer == NULL) return 0;
	if(stk->top >= DFSWITH_STACKSIZE)  //>= or ==
	{
		printf("Stack is overflow!!!\n");
		return 0;
	}
	stk->stkPointer[stk->top++] = data;


	return 1;
}

/*
* 回过头来看为啥要返回 BITNODE* 的数据而不是 BITNODE的
*/
BITNODE* PopStackBit(STACK* const stk)
{
	BITNODE* tmp = NULL;
	// if(stk->stkPointer == NULL) return NULL;
	tmp = stk->stkPointer[--stk->top];
	return tmp;
}

/**
 * 判断栈是否空
 * empety-1 not empety-0
 * */
int IsStackEmpetyBit(STACK* stk)
{
	if(stk->top <= 0) return 1;
	else 			return 0;
}

/**
 * 这里好像不用输入指针变量也行
 * @remark:通过stack来辅助DFS,入栈的元素是节点指针
 * */
void DFSWithStack(BITNODE* const treeNode)
{
	if(treeNode == NULL) return ;
	BITNODE* temp = treeNode;
	STACK stk;
	stk.stkPointer = (BITNODE**)malloc(sizeof(BITNODE*)*DFSWITH_STACKSIZE);
	stk.size       = DFSWITH_STACKSIZE;
	stk.top 		= 0;
	//根节点先入栈
	// PushStackBit(&stk,temp);

	//栈中数据不为空时说明还有结点没有遍历到
	/*下面是主体部分：
		对于一个节点来说，如果该节点有左子节点都应该入左子节点，
		然后再入右子节点。根节点同样适用
		截止条件应该是栈为空，否则就一直执行
	*/

	do
	{
		//将该节点的左子节点入栈，直到该节点的左子节点为空
		while(temp != NULL)
		{
			// temp = temp->lChild;
			PushStackBit(&stk,temp);
			temp = temp->lChild;

		}

		temp = PopStackBit(&stk);
		printf("%d ",temp->data);fflush(stdout);
		temp = temp->rChild;

	}while(IsStackEmpetyBit(&stk) != 1 || NULL != temp);

	FREE(stk.stkPointer);
}

/**
 * BFS 广度优先搜索 使用队列进行辅助
 * @remark:无法使用前面写的队列，因为入队的元素不是整型int，只能重新写
 * */
#define QUEUE_ELEMENT_TYPE BITNODE*
typedef struct queue
{
	int tail;
	int head;
	QUEUE_ELEMENT_TYPE*  quePointer; //内存的地址
}QUEUE;

void BSP(const BITNODE* const treeNode)
{
	if(treeNode == NULL) return ;
	const BITNODE* temp = treeNode;
	QUEUE que;
	que.quePointer = (QUEUE_ELEMENT_TYPE*)malloc(sizeof(QUEUE_ELEMENT_TYPE) * QUEUE_SIZE);
	que.head = 0;
	que.tail = 0;

	// 头结点入队
	que.quePointer[que.tail++] = temp;
	while (que.tail != que.head)
	{
		temp = que.quePointer[que.head++];
		printf("%d ",temp->data);
		// 该节点的左右节点依次入栈
		if(temp->lChild != NULL)
		{
			que.quePointer[que.tail++] = temp->lChild;
		}
		if(temp->rChild != NULL)
		{
			que.quePointer[que.tail++] = temp->rChild;
		}
		// assert(que.tail <= que.head);

	}

	FREE(que.quePointer);

}

void dfs(const BITNODE* const root ,int depth,int* returnSize,int* ret_arr)
{
    if(root == NULL) return ;

    *returnSize = ( *returnSize > depth ? *returnSize : depth );
    ret_arr[depth] = root->data;

    dfs(root->lChild,depth+1,returnSize,ret_arr);
    dfs(root->rChild,depth+1,returnSize,ret_arr);

}

// DFS
int* rightSideView(const BITNODE* const root, int* returnSize)
{
    if(root == NULL) return NULL;

    int* ret_arr = (int *)malloc(sizeof(int) * 101);
    memset(ret_arr,0,101);
    *returnSize = 0;

    dfs(root,0,returnSize,ret_arr);

    return ret_arr;
}

#ifdef BINARY_TREE_DEBUG
// 后期考虑加一个二叉树图形化的功能
int main(int argc, char const *argv[])
{
	BITNODE* T;
	int deepth = 0;
	int num = 0;
	printf("请输入第一个节点的值，0代表没有叶子节点:\n");
	CreateTree(&T);
    printf("先序遍历二叉树:\n");
    PreOrder(T);
    printf("\n");
    printf("中序遍历二叉树:\n");
    MidOrder(T);
    printf("\n");
    printf("后序遍历二叉树:\n");
    PostOrder(T);
    printf("\n");
    LeafCount(T,&num);
    printf("二叉树的叶子节点个数为:%d\n",num);
    printf("\n");
    printf("DFS:\n");
    DFS(T);
    printf("\n");
    printf("DFSWithStack:\r\n");
    DFSWithStack(T);
    printf("\n");
	printf("BSP:\r\n");
	BSP(T);
	printf("\r\n");

	int returnSize = 0;
	int* ret_arr;
	ret_arr = rightSideView(T,&returnSize);
	for(int i = 0;i < returnSize;i ++)
	{
		printf("%d ",ret_arr[i]);
	}printf("\n");

	return 0;
}

#endif
